package a_sorting_basic.c_insertion_sort;

import a_sorting_basic.c_insertion_sort.sorting_helper.SortingTestC;
import utils.ArrayGeneric;

/**
 * 3- 冒泡排序
 * 均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
 * O（n^2）	    O（n^2）	    O（1）	    是
 * 整体效率不如插入排序， 但是比较经典
 * 从前到后两两交换， 每次将一个最大的交换到后边
 * 外层循环次数： 从第二个元素开始遍历
 * 内层循环次数： 每个元素和前面的元素比较和交换
 * 优化点1： 每次缩小交换的范围， 因为后边是已经排序好的元素， 可以不需比较
 * 优化点2： 可以每次记录最后一次交换的位置， 后面的可以不需比较， 但是由于引入了新的变量， 实际效果更差, 因此不采纳
 */
@SuppressWarnings("unchecked")
public class BubbleSortC extends SortingTestC {

    @Override
    public void sort(ArrayGeneric arr) {
        int len = arr.length();
        boolean swapped;
//        int pos = 0; // 记录最后一次交换的位置， 理论上有效， 实际效果更差
        do {
            swapped = false;
            for (int i = 1; i < len; i++) {
                if (arr.get(i - 1).compareTo(arr.get(i)) > 0) {
                    arr.swap(i - 1, i);
                    swapped = true;
//                    pos = len; // 因为每次记录pos的位置， 导致实际效果更差
                }
            }
//            len = pos; // 最后一次交换的位置及其之后的位置可以都不需考虑
            len--; // 后面是已经排序好的元素， 可以不需比较
        } while (swapped);
    }
}
